package com.cyc.basic.leecode.链表;

/**
 * 自定义链表
 * @author fei
 */
public class ListNode {
    //自定义链表节点, 节点中包含自己的值和下一节点的引用
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/**
 * 自定义链表结构, 属性包含size和链表头
 */
class MyLinkedList {

    int size;
    ListNode head;  // sentinel node as pseudo-head 哨兵节点被用作伪头节点, 这个head并不是真正的头节点

    public MyLinkedList() {
        size = 0;
        //下面那个0只是起到一个占位符的作用, 下面填其他值也可以
        head = new ListNode(0);
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        // if index is invalid
        if (index < 0 || index >= size) {
            return -1;
        }

        ListNode curr = head;
        // index steps needed
        // to move from sentinel node to wanted index
        for (int i = 0; i < index + 1; ++i) {
            //从伪头节点开始, 第一次curr.next获取到的就是真-头节点,然后依次遍历获取下一节点
            curr = curr.next;
        }
        return curr.val;
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        // If index is greater than the length,
        // the node will not be inserted.
        if (index > size) {
            return;
        }

        // [so weird] If index is negative,
        // the node will be inserted at the head of the list.
        if (index < 0) {
            index = 0;
        }

        ++size;
        // find predecessor of the node to be added
        //找到要插入位置节点的前驱节点。如果要在头部插入，则它的前驱节点就是伪头。如果要在尾部插入节点，则前驱节点就是尾节点。
        //通过改变 next 来插入节点。
        ListNode pred = head;
        for (int i = 0; i < index; ++i) {
            pred = pred.next;
        }

        // node to be added
        ListNode toAdd = new ListNode(val);
        // insertion itself
        //新增的toAdd节点的下一个节点 , 就是原来pred的下一个节点
        toAdd.next = pred.next;
        //pred的下一个节点 , 就是现在的toAdd
        pred.next = toAdd;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        // if the index is invalid, do nothing
        if (index < 0 || index >= size) {
            return;
        }

        size--;
        // find predecessor of the node to be deleted
        //找到要删除节点的前驱节点, 也就是他前面那个节点
        ListNode pred = head;
        for (int i = 0; i < index; ++i) {
            pred = pred.next;
        }

        // delete pred.next
        pred.next = pred.next.next;
    }
}